Field
This disclosure relates to the field of computation. More particularly, this disclosure relates to methods for assessing pseudorandom number streams.
Description of the Related Art
Random number generators, which generate streams of seemingly random numbers, are used in many computing applications. An application may use a single stream of random numbers or multiple streams of random numbers simultaneously. A sequential random number generator is designed to generate a single stream of random numbers, the starting point of which may be changed with the initial (seed) value. A parallel random number generator (PRNG) is designed to generate multiple, independent streams of random numbers simultaneously with a simple change in a parameter used to initialize the random number streams.
It is often useful to test a random number generator to assess the quality of the random number stream. Some single-stream statistical test batteries provide pass/fail indication for each test in the battery, since it may not be meaningful to combine the statistical computations from multiple tests to provide an overall quality metric for the RNG (random number generator) tested. Therefore, it is common to use the test results as a multi-bit vector data, with each bit representing the pass/fail status for a test. The statistical test batteries do not provide a single quantitative metric to compare the two generators. This could be a limitation if two RNGs that need to be compared fail different tests.
Single-stream tests may be ineffective for testing the correlations of random numbers among a large number (e.g., thousands to billions) of parallel random number streams since the a typical single-stream test method may operate on blocks of a few thousands of numbers at a time. Typical existing test methods may be considered off-line methods in the sense that the tests are fed with data generated by the random number generator that is being evaluated specifically for test purposes.
Parallel random number streams may be generated by a parameterized family of pseudorandom number generators, by a collection of true random number generators that generate random numbers based on environmental signals such as noise levels and temperature, computing and communication delays, events induced by computer users or other sources, or any combination of the pseudo- and true random number generators. The quality of the random numbers used may be crucial for quick and accurate results from computer-based simulations and for robust security protocols and security keys used in security protocols.
Some methods to test and assess the independence of parallel random number streams are typically based on sequential test methods that are designed to test intra-stream correlations of a single random number stream. One practice for statistical testing of PRNG quality is to generate parallel streams, interleave them to form a single stream, and apply single-stream tests to the interleaved stream. If the interleaved stream passes most or all of the single-stream tests, then the PRNG may be deemed to be of good quality and is accepted for use in applications.